package com.kobeliu.entity;

import com.kobeliu.entity.Demo_39_sword_32.*;

import java.util.*;

/**
 * 剑指 32
 *
 * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
 *
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回其层次遍历结果：
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 */

public class Demo_40_sword_32 {

    public static void main(String[] args) {


    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>(); //总数组
        if(root== null) return lists;
        List<Integer> list1 = new ArrayList<>(); //每一层的数组
        Queue<TreeNode> queue = new LinkedList<>(); //放节点的队列
        queue.add(root); //头节点进队
        int sum = 1; //一开始的一层 一定是1个 每一次sum=0时，回头去看下队列里面还有多少个数，个数就是下一层的总个数
        list1.add(root.val);
        lists.add(list1);
        TreeNode temp;

        while(queue.size()>0){
            temp = queue.poll();
            list1.add(temp.val);
            if(--sum==0){
                List<Integer> newList = new ArrayList<>();
                newList.addAll(list1);
                lists.add(newList);
                //代表一层结束了
                list1.clear();
            }

            if(temp.left!=null) queue.add(temp.left);
            if(temp.right!=null) queue.add(temp.right);
            if(sum==0){
                sum = queue.size();
            }
        }

        if(list1.size()>0){
            lists.add(list1);
        }


        return lists;

    }
}
